1.Field of the Invention
The present invention relates to packet routing in telecommunication systems, and, more particularly, to determining paths through nodes of a packet network for routing of packets with guaranteed service levels for restorable connections.
2. Description of the Related Art
In interconnected communications networks, such as the Internet, users establish connections between a source and a destination with a stream of data packets, called packet flows, that are transferred through the network over a network path. Packet networks are typically characterized by a set of routers connected via links, and optical networks, while not necessarily packet-based, are similarly configured with optical switches interconnected by optical links. A network path is defined by a set of nodes (routers or optical switches) interconnected by a set of links. Packet and optical networks may have a hierarchical structure in which smaller networks are interconnected by larger networks, and a peer structure in which equivalent networks are interconnected. A network connects to one or more other external networks through ingress nodes (those nodes receiving data from external networks) and egress nodes (those nodes transferring data to external networks). Nodes may be, for example, routers in a packet network or optical terminals in an optical network.
Interior routing protocols are employed by routers to determine forwarding of packets between a source and destination pair along a path through the nodes of the interconnected packet network. Packets received by a node's router are forwarded to other nodes based on a forwarding table constructed in accordance with the interior routing protocol or routes installed with explicit route provisioning. Interior routing protocols may also specify exchange network topology and link-state information (“network topology information”) among routers to allow the node's router to construct the corresponding forwarding table. An example of a widely used interior routing protocol for “best effort” routing is the Open Shortest Path First (OSPF) protocol. In addition, some routing protocols associate a link “cost” with each link between nodes. This link cost may be associated with, for example, average link utilization or revenue generated by the link, as well as link importance in the network. When link-state information or link-bandwidth (e.g., connectivity or available bandwidth) is exchanged between routers, each router in the network has a complete description of the network's topology.
Since routing of packets at the higher levels is desirably performed at high speed, each higher-level packet network may use its own interior routing protocol in addition to the interior routing protocol of the lower-level packet network. Routing protocols, in addition to providing connectivity, may also enable traffic management. The Multi-Protocol Label Switched (MPLS) standard, for example, allows such routing protocols in backbone networks. The MPLS standard may be employed for networks having virtual circuits (packet flows) with provisioned service levels (also known as guaranteed quality-of-service (QoS)).
Provisioned service levels may be, for example, a guaranteed minimum bandwidth for the path of a packet flow through the backbone network. This path having a guaranteed level of service between ingress and egress points may be referred to as a Network Tunnel Path (NTP). As would be apparent to one skilled in the art, specific implementations of NTPs, exist for different types of networks. As examples of NTPs, virtual circuits may be established for packet flows in TCP/IP networks, virtual circuits may be established for cells in Asynchronous Transfer Mode (ATM) networks, and label switched paths (LSPs) may be established for packets in MPLS networks. Packets of a signaling protocol, such as RSVP (Reservation Protocol for IP and MPLS networks) or LDP (Label Distribution Protocol) for MPLS networks, may be used to reserve link bandwidth and establish an NTP, once routing for the NTP, is calculated. NTPs may be provisioned as an explicit route along specific paths between nodes of the backbone network (i.e., when an NTP is provisioned, all intermediate points may be specified through which a packet passes between the ingress and egress points of the NTP).
To generate a forwarding table, each router computes a set of preferred paths through the network nodes, and may use the weights to calculate the set of preferred paths. Each preferred path has a minimum total weight between nodes as well as minimum summed weight through nodes of the path, which is known in the art as shortest-path routing. This set of preferred paths may be defined with a shortest-path tree (SPT). The forwarding table with routing information (e.g., source-destination pair, source ports, and destination ports) is generated from the SPT. The router uses the routing information to forward a received packet to its destination along the shortest path of the SPT. The SPT may be calculated using an algorithm such as Dijkstra's algorithm, described in E. Dijkstra, “A Note: Two Problems In Connection With Graphs,” Numerical Mathematics, vol.1, 1959, pp. 269-271.
Restoring service after link failure(s) is an important aspect of both packet and optical networks. For restoration, each connection is routed along two disjoint paths through the network: a primary (active path) and a secondary (backup) path. The backup path is used for restoring connectivity if the active path fails. For some networks, capacity in links of the backup path may be shared between different connections for bandwidth efficiency. For sharing to be possible, the nodes performing route computations must know the amount of bandwidth on each link that is currently used for providing backup capacity. While this information might be disseminated according to link-state routing protocols, the information might only include link status and the bandwidth used for carrying active paths. Sharing might not be possible when the sender simultaneously transmits on both paths and the receiver chooses to receive data from the path with the strong signal, such as in optical networks. Simultaneous transmission is often employed in optical networks despite its bandwidth inefficiency because it allows relatively quick and simple restoration (only the receiver needs to detect and act upon failure).